import java.util.Arrays;

/**
 * 283. 移动零
 */
public class Solution_283 {
    /**
     * 双指针
     * <p>
     * 时间复杂度：O(N)
     * <p>
     * 空间复杂度：O(1)
     */
    public void moveZeroes(int[] nums) {
        int len = nums.length;
        // left 指向第一个 0，right 指向第一个非 0
        // left 左边均为非零数；right 左边直到 left 处均为零。
        int left = 0, right = 0;
        /*
          0 1 0 3 12
          1 0 0 3 12
          1 3 0 0 12
          1 3 12 0 0
        */
        while (right < len) {
            if (nums[right] != 0) {
                swap(nums, left, right);
                left++;
            }
            right++;
        }
    }

    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    /**
     * 借用额外数组，不符合题目要求，只作为一种思路
     */
    public void moveZeroes1(int[] nums) {
        int len = nums.length;
        int[] temp = new int[len];
        int j = 0;
        for (int i = 0; i < len; i++) {
            if (nums[i] != 0) {
                temp[j] = nums[i];
                j++;
            }
        }
        System.arraycopy(temp, 0, nums, 0, len);
    }

    public static void main(String[] args) {
        Solution_283 solution = new Solution_283();
        int[] nums = { 0, 1, 0, 3, 12 };
        solution.moveZeroes(nums);
        System.out.println(Arrays.toString(nums));
    }
}
